package LeetCode;

public class LC_678_ValidParenthesisString {

    public static void main(String[] args) {

    }

    class Solution {
        private boolean helper(int left, int right, String s, int pos) {
            if (left < right) return false;
            if (pos == s.length()) return left == right;
            if (s.charAt(pos) == '(') {
                if (helper(left + 1, right, s, pos + 1)) {
                    return true;
                }
            } else if (s.charAt(pos) == ')') {
                if (helper(left, right + 1, s, pos + 1) ) {
                    return true;
                }
            } else if (s.charAt(pos) == '*') {
                if (helper(left + 1, right, s, pos + 1) || helper(left, right + 1, s, pos + 1) || helper(left, right, s, pos + 1)) {
                    return true;
                }
            }
            return false;
        }
        public boolean checkValidString(String s) {
            return s == null || s.length() < 1 || helper(0, 0, s, 0);
        }
    }

}